from typing import List

# 该问题拥有最优子结构和无后效性所以可用dp
# 可以使用滚动数组远离 讲dp数组优化为width长度

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        if obstacleGrid[0][0] == 1 or obstacleGrid[-1][-1] == 1:
            return 0
        # 获取宽和高
        width = len(obstacleGrid[0])
        height = len(obstacleGrid)

        # 初始化dp数字全为0
        dp = [[0] * width for _ in range(height)]

        # 从左到右从上到下遍历，可以保证每一个格子的左和上方格子在之前已经处理过
        for i in range(height):
            for j in range(width):
                if obstacleGrid[i][j] == 0:  # 当无障碍时需要处理
                    if i == 0 and j == 0:  # 处理特殊情况 首位
                        dp[0][0] = 1
                    elif i == 0:  # 处理特殊情况 首行
                        dp[i][j] = dp[i][j - 1]
                    elif j == 0:  # 处理特殊情况 首列
                        dp[i][j] = dp[i - 1][j]
                    else: # 一般情况，路线数量等于上和左格子路线数量总和
                        dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
                else:  # 有障碍时，直接跳过默认为0
                    pass

        return dp[-1][-1]


if __name__ == "__main__":
    mySol = Solution()
    al = [1, 2, 3, 2, 1, 0, 1]
    bl = [3, 2, 1, 0, 1, 4, 7]
    myStr = 'abcdefghijk'
    s = 'abc'
    p = 'ac'
    myLL = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
    # al = [0, 0, 0, 0, 1]
    # bl = [1, 0, 0, 0, 0]
    print('feedback:', mySol.uniquePathsWithObstacles(myLL))
